package code.starivan.leetcode;

/**
 * Created by Ivan on 2015/10/27.
 */

/*
A robot is located at the top-left corner of a m x n grid (marked 'Start' in the diagram below).

        The robot can only move either down or right at any point in time. The robot is trying to reach the bottom-right corner of the grid (marked 'Finish' in the diagram below).

        How many possible unique paths are there?


        Above is a 3 x 7 grid. How many possible unique paths are there?

        Note: m and n will be at most 100.
*/

public class N062_UniquePaths {
    public static void test(){
        System.out.println(new N062_UniquePaths().uniquePaths(2,4));
    }
    public int uniquePaths(int m, int n) {
        if(m<=0||n<=0){
            return 0;
        }

        if(m<n){
            int tmp=m;
            m=n;
            n=tmp;
        }

        int[] steps=new int[n];
        for(int i=0;i<n;++i){
            steps[i]=1;
        }

        for(int r=1;r<m;++r){
            for(int i=1;i<n;++i){
                steps[i]=steps[i]+steps[i-1];
            }
        }

        return steps[n-1];
    }
}
